package LeetCodeSection;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 20
 *@time:      14:22
 *
 */

//2.
//另外一颗树的子树
//https://leetcode.cn/problems/subtree-of-another-tree/
public class ASubtreeOfAnotherTree {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    class Solution {
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if (root == null) return false;
            if (isSameTree(root, subRoot)) {
                return true;
            }
            if (isSubtree(root.left, subRoot)) {
                return true;
            }
            if (isSubtree(root.right, subRoot)) {
                return true;
            }
            return false;
        }
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if ((p == null && q != null) || (p != null && q == null)) {
                return false;
            }

            if (p == null && q == null) {
                return true;
            }

            if (p.val != q.val) {
                return false;
            }

            return isSameTree(p.left, q.left)
                    && isSameTree(p.right, q.right);

        }
    }
}
